package solution;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-03-11
 * Time: 20:32
 */

//https://leetcode.cn/problems/copy-list-with-random-pointer/submissions/412014267/
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}


class Solution {
    Map<Node, Node> hm = new HashMap<>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (!hm.containsKey(head)) {
            Node newHead = new Node(head.val);
            hm.put(head, newHead);
            newHead.next = copyRandomList(head.next);
            newHead.random = copyRandomList(head.random);
        }
        return hm.get(head);
    }
}


//miao
//
//class Solution {
//    public Node copyRandomList(Node head) {
//        if (head == null) {
//            return null;
//        }
//        Map<Node, Node> hm = new HashMap<>();
//        Node cur = head;
//        while (cur != null) {
//            hm.put(cur, new Node(cur.val));
//            cur = cur.next;
//        }
//        cur = head;
//        while (cur != null) {
//            hm.get(cur).next = hm.get(cur.next);
//            hm.get(cur).random = hm.get(cur.random);
//            cur = cur.next;
//        }
//        return hm.get(head);
//    }
//}



//class Solution {
//    public Node copyRandomList(Node head) {
//        if (head == null) {
//            return null;
//        }
//        for (Node node = head; node != null; node = node.next.next) {
//            Node newNode = new Node(node.val);
//            newNode.next = node.next;
//            node.next = newNode;
//        }
//        for (Node node = head; node != null; node = node.next.next) {
//            Node newNode = node.next;
//            newNode.random = node.random != null ? node.random.next : null;
//        }
//        Node headNow = head.next;
//        for (Node node = head; node != null; node = node.next) {
//            Node newNode = node.next;
//            node.next = node.next.next;
//            newNode.next = newNode.next != null ? newNode.next.next : null;
//        }
//        return headNow;
//    }
//}